//n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 
//
// 
// 
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 4
//输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[["Q"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 
// 
// 
// Related Topics 数组 回溯 👍 1284 👎 0

package leetcode.editor.cn;

import java.util.*;

class NQueens {
    public static void main(String[] args) {
        Solution solution = new NQueens().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<String>> solveNQueens(int n) {
            if (n == 0) {
                return res;
            }

            // 需要将二维数组全部赋值，防止出现空字符
            char[][] chars = new char[n][n];
            for (char[] num : chars) {
                Arrays.fill(num, '.'); // 将指定的char值分配给指定的char数组的每个元素
            }

            backtracking(n, 0, chars);
            return res;
        }

        List<List<String>> res = new ArrayList<>();

        /**
         * 回溯搜索
         *
         * @param n          表示输入的棋盘大小
         * @param row        表示当前遍历到第几行了
         * @param chessboard 表示棋盘（ ‘.’ 表示空格，‘Q’表示皇后）
         */
        public void backtracking(int n, int row, char[][] chessboard) {
            if (row == n) {
                res.add(numToList(chessboard));// 此行
                return;
            }

            for (int col = 0; col < n; col++) {   // for遍历每列
                if (isValid(row, col, n, chessboard)) {
                    chessboard[row][col] = 'Q'; // 放置皇后
                    backtracking(n, row + 1, chessboard); // 递归遍历每行，注意row需要加一
                    chessboard[row][col] = '.'; // 回溯
                }
            }
        }


        /**
         * 二维字符数组转化为List集合
         *
         * @param chessboard
         * @return
         */
        public List<String> numToList(char[][] chessboard) {
            List<String> list = new ArrayList<>();

            for (char[] num : chessboard) {
                list.add(String.valueOf(num));
            }

            return list;
        }


        /**
         * 判断是否满足n皇后的条件
         *
         * @param row
         * @param col
         * @param chessboard
         * @return
         */
        public boolean isValid(int row, int col, int n, char[][] chessboard) {
            // 判断一列一列是否有皇后
            for (int i = 0; i < row; i++) {
                if (chessboard[i][col] == 'Q')
                    return false;
            }

            // 判断135度是否有皇后
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
                if (chessboard[i][j] == 'Q')
                    return false;
            }

            // 判断45度是否有皇后
            for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
                if (chessboard[i][j] == 'Q')
                    return false;
            }

            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
